package com.shm.leetcode;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * 480. 滑动窗口中位数
 * 中位数是有序序列最中间的那个数。如果序列的大小是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
 *
 * 例如：
 *
 * [2,3,4]，中位数是 3
 * [2,3]，中位数是 (2 + 3) / 2 = 2.5
 * 给你一个数组 nums，有一个大小为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
 *
 *
 *
 * 示例：
 *
 * 给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
 *
 * 窗口位置                      中位数
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       1
 *  1 [3  -1  -3] 5  3  6  7      -1
 *  1  3 [-1  -3  5] 3  6  7      -1
 *  1  3  -1 [-3  5  3] 6  7       3
 *  1  3  -1  -3 [5  3  6] 7       5
 *  1  3  -1  -3  5 [3  6  7]      6
 *  因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
 *
 *
 *
 * 提示：
 *
 * 你可以假设 k 始终有效，即：k 始终小于输入的非空数组的元素个数。
 * 与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。
 * @author SHM
 */
public class MedianSlidingWindow {
    /**
     * 前言
     * 本题是 295. 数据流的中位数 的进阶版本。
     *
     * 我们首先思考一下完成本题需要做哪些事情：
     *
     * 初始时，我们需要将数组 \textit{nums}nums 中的前 kk 个元素放入一个滑动窗口，并且求出它们的中位数；
     *
     * 随后滑动窗口会向右进行移动。每一次移动后，会将一个新的元素放入滑动窗口，并且将一个旧的元素移出滑动窗口，最后再求出它们的中位数。
     *
     * 因此，我们需要设计一个「数据结构」，用来维护滑动窗口，并且需要提供如下的三个接口：
     *
     * \texttt{insert(num)}insert(num)：将一个数 \textit{num}num 加入数据结构；
     *
     * \texttt{erase(num)}erase(num)：将一个数 \textit{num}num 移出数据结构；
     *
     * \texttt{getMedian()}getMedian()：返回当前数据结构中所有数的中位数。
     *
     * 方法一：双优先队列 + 延迟删除
     * 思路与算法
     *
     * 我们可以使用两个优先队列（堆）维护所有的元素，第一个优先队列 \textit{small}small 是一个大根堆，它负责维护所有元素中较小的那一半；第二个优先队列 \textit{large}large 是一个小根堆，它负责维护所有元素中较大的那一半。具体地，如果当前需要维护的元素个数为 xx，那么 \textit{small}small 中维护了 \lceil \frac{x}{2} \rceil⌈
     * 2
     * x
     * ​
     *  ⌉ 个元素，\textit{large}large 中维护了 \lfloor \frac{x}{2} \rfloor⌊
     * 2
     * x
     * ​
     *  ⌋ 个元素，其中 \lceil y \rceil⌈y⌉ 和 \lfloor y \rfloor⌊y⌋ 分别表示将 yy 向上取整和向下取整。也就是说：
     *
     * \textit{small}small 中的元素个数要么与 \textit{large}large 中的元素个数相同，要么比 \textit{large}large 中的元素个数恰好多 11 个。
     *
     * 这样设计的好处在于：当二者包含的元素个数相同时，它们各自的堆顶元素的平均值即为中位数；而当 \textit{small}small 包含的元素多了一个时，\textit{small}small 的堆顶元素即为中位数。这样 \texttt{getMedian()}getMedian() 就设计完成了。
     *
     * 而对于 \texttt{insert(num)}insert(num) 而言，如果当前两个优先队列都为空，那么根据元素个数的要求，我们必须将这个元素加入 \textit{small}small；如果 \textit{small}small 非空（显然不会存在 \textit{small}small 空而 \textit{large}large 非空的情况），我们就可以将 \textit{num}num 与 \textit{small}small 的堆顶元素 \textit{top}top 比较：
     *
     * 如果 \textit{num} \leq \textit{top}num≤top，我们就将其加入 \textit{small}small 中；
     *
     * 如果 \textit{num} > \textit{top}num>top，我们就将其加入 \textit{large}large 中。
     *
     * 在成功地加入元素 \textit{num}num 之后，两个优先队列的元素个数可能会变得不符合要求。由于我们只加入了一个元素，那么不符合要求的情况只能是下面的二者之一：
     *
     * \textit{small}small 比 \textit{large}large 的元素个数多了 22 个；
     *
     * \textit{small}small 比 \textit{large}large 的元素个数少了 11 个。
     *
     * 对于第一种情况，我们将 \textit{small}small 的堆顶元素放入 \textit{large}large；对于第二种情况，我们将 \textit{large}large 的堆顶元素放入 \textit{small}small，这样就可以解决问题了，\texttt{insert(num)}insert(num) 也就设计完成了。
     *
     * 然而对于 \texttt{erase(num)}erase(num) 而言，设计起来就不是那么容易了，因为我们知道，优先队列是不支持移出非堆顶元素这一操作的，因此我们可以考虑使用「延迟删除」的技巧，即：
     *
     * 当我们需要移出优先队列中的某个元素时，我们只将这个删除操作「记录」下来，而不去真的删除这个元素。当这个元素出现在 \textit{small}small 或者 \textit{large}large 的堆顶时，我们再去将其移出对应的优先队列。
     *
     * 「延迟删除」使用到的辅助数据结构一般为哈希表 \textit{delayed}delayed，其中的每个键值对 (\textit{num}, \textit{freq})(num,freq)，表示元素 \textit{num}num 还需要被删除 \textit{freq}freq 次。「优先队列 + 延迟删除」有非常多种设计方式，体现在「延迟删除」的时机选择。在本题解中，我们使用一种比较容易编写代码的设计方式，即：
     *
     * 我们保证在任意操作 \texttt{insert(num)}insert(num)，\texttt{erase(num)}erase(num)，\texttt{getMedian()}getMedian() 完成之后（或者说任意操作开始之前），\textit{small}small 和 \textit{large}large 的堆顶元素都是不需要被「延迟删除」的。这样设计的好处在于：我们无需更改 \texttt{getMedian()}getMedian() 的设计，只需要略加修改 \texttt{insert(num)}insert(num) 即可。
     *
     * 我们首先设计一个辅助函数 \texttt{prune(heap)}prune(heap)，它的作用很简单，就是对 \textit{heap}heap 这个优先队列（\textit{small}small 或者 \textit{large}large 之一），不断地弹出其需要被删除的堆顶元素，并且减少 \textit{delayed}delayed 中对应项的值。在 \texttt{prune(heap)}prune(heap) 完成之后，我们就可以保证 \textit{heap}heap 的堆顶元素是不需要被「延迟删除」的。
     *
     * 这样我们就可以在 \texttt{prune(heap)}prune(heap) 的基础上设计另一个辅助函数 \texttt{makeBalance()}makeBalance()，它的作用即为调整 \textit{small}small 和 \textit{large}large 中的元素个数，使得二者的元素个数满足要求。由于有了 \texttt{erase(num)}erase(num) 以及「延迟删除」，我们在将一个优先队列的堆顶元素放入另一个优先队列时，第一个优先队列的堆顶元素可能是需要删除的。因此我们就可以用 \texttt{makeBalance()}makeBalance() 将 \texttt{prune(heap)}prune(heap) 封装起来，它的逻辑如下：
     *
     * 如果 \textit{small}small 和 \textit{large}large 中的元素个数满足要求，则不进行任何操作；
     *
     * 如果 \textit{small}small 比 \textit{large}large 的元素个数多了 22 个，那么我们我们将 \textit{small}small 的堆顶元素放入 \textit{large}large。此时 \textit{small}small 的对应元素可能是需要删除的，因此我们调用 \texttt{prune(small)}prune(small)；
     *
     * 如果 \textit{small}small 比 \textit{large}large 的元素个数少了 11 个，那么我们将 \textit{large}large 的堆顶元素放入 \textit{small}small。此时 \textit{large}large 的对应的元素可能是需要删除的，因此我们调用 \texttt{prune(large)}prune(large)。
     *
     * 此时，我们只需要在原先 \texttt{insert(num)}insert(num) 的设计的最后加上一步 \texttt{makeBalance()}makeBalance() 即可。然而对于 \texttt{erase(num)}erase(num)，我们还是需要进行一些思考的：
     *
     * 如果 \textit{num}num 与 \textit{small}small 和 \textit{large}large 的堆顶元素都不相同，那么 \textit{num}num 是需要被「延迟删除」的，我们将其在哈希表中的值增加 11；
     *
     * 否则，例如 \textit{num}num 与 \textit{small}small 的堆顶元素相同，那么该元素是可以理解被删除的。虽然我们没有实现「立即删除」这个辅助函数，但只要我们将 \textit{num}num 在哈希表中的值增加 11，并且调用「延迟删除」的辅助函数 \texttt{prune(small)}prune(small)，那么就相当于实现了「立即删除」的功能。
     *
     * 无论是「立即删除」还是「延迟删除」，其中一个优先队列中的元素个数发生了变化（减少了 11），因此我们还需要用 \texttt{makeBalance()}makeBalance() 调整元素的个数。
     *
     * 此时，所有的接口都已经设计完成了。由于 \texttt{insert(num)}insert(num) 和 \texttt{erase(num)}erase(num) 的最后一步都是 \texttt{makeBalance()}makeBalance()，而 \texttt{makeBalance()}makeBalance() 的最后一步是 \texttt{prune(heap)}prune(heap)，因此我们就保证了任意操作完成之后，\textit{small}small 和 \textit{large}large 的堆顶元素都是不需要被「延迟删除」的。
     *
     * 具体实现的细节相对较多，读者可以参考下面的代码和注释进一步理解。
     * 复杂度分析
     *
     * 由于「延迟删除」的存在，\textit{small}small 比 \textit{large}large 在最坏情况下可能包含所有的 nn 个元素，即没有一个元素被真正删除了。因此优先队列的大小是 O(n)O(n) 而不是 O(k)O(k) 的，其中 nn 是数组 \textit{nums}nums 的长度。
     *
     * 时间复杂度：O(n\log n)O(nlogn)。\texttt{insert(num)}insert(num) 和 \texttt{erase(num)}erase(num) 的单次时间复杂度为 O(\log n)O(logn)，\texttt{getMedian()}getMedian() 的单次时间复杂度为 O(1)O(1)。因此总时间复杂度为 O(n\log n)O(nlogn)。
     *
     * 空间复杂度：O(n)O(n)。即为 \textit{small}small，\textit{large}large 和 \textit{delayed}delayed 需要使用的空间。
     *
     * 结语
     * 读者可以尝试回答如下的两个问题来检验自己是否掌握了该方法：
     *
     * 在 \texttt{insert(num)}insert(num) 的最后我们加上了一步 \texttt{makeBalance()}makeBalance()，其中包括可能进行的 \texttt{prune(heap)}prune(heap) 操作，这对于 \texttt{insert(num)}insert(num) 操作而言是否是必要的？
     *
     * 在 \texttt{insert(num)}insert(num) 的过程中，如果我们将 \texttt{insert(num)}insert(num) 放入了 \textit{large}large 中，并且 \textit{num}num 恰好出现在 \textit{large}large 的堆顶位置，且两个优先队列的元素个数满足要求，不需要进行调整。此时会不会出现 \textit{num}num 是一个需要被「延迟删除」的元素的情况，这样就不满足在 \texttt{insert(num)}insert(num) 操作完成之后 \textit{large}large 的堆顶是不需要被「延迟删除」的要求了？
     *
     * 答案
     *
     * 实际上是不必要的。因为在 \texttt{insert(num)}insert(num) 操作之前，两个优先队列的堆顶元素都是不需要被删除的，而我们只可能从那个被加入了一个元素的优先队列的堆顶元素放入另一个优先队列中，因此两个优先队列的堆顶元素仍然都是不需要被删除的。这样写只是为了将 \texttt{insert(num)}insert(num) 和 \texttt{erase(num)}erase(num) 操作统一起来，减少代码的冗余。
     *
     * 不可能会出现这种情况，假设出现了这种情况，那么 \textit{num}num 显然不会等于 \textit{large}large 原先的堆顶元素，因为 \textit{large}large 原先的堆顶元素一定是不需要被删除的。那么 \textit{num}num 满足：
     *
     * \textit{small} ~的堆顶元素 < \textit{num} < \textit{large} ~的堆顶元素
     * small 的堆顶元素<num<large 的堆顶元素
     *
     * 由于 \textit{small}small 是大根堆，\textit{large}large 是小根堆，因此根本就不存在与 \textit{num}num 值相同的元素，也就不可能会被延迟删除了。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/sliding-window-median/solution/hua-dong-chuang-kou-zhong-wei-shu-by-lee-7ai6/
     * @param nums
     * @param k
     * @return
     */
    public double[] medianSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        DualHeap dualHeap = new DualHeap(k);
        for (int i = 0; i < k; i++) {
            dualHeap.insert(nums[i]);
        }
        double[] ans = new double[n-k+1];
        ans[0] = dualHeap.getMedian();
        for (int i = k; i < n; i++) {
            dualHeap.insert(nums[i]);
            dualHeap.erase(nums[i-k]);
            ans[i-k+1] = dualHeap.getMedian();
        }
        return ans;
    }

    class DualHeap{
        // 大根堆，维护较小的一半元素
        PriorityQueue<Integer> small;
        // 小根堆，维护较大的一半元素
        PriorityQueue<Integer> large;
        // small 和 large 当前包含的元素个数，需要扣除被「延迟删除」的元素
        int smallSize,largeSize;
        int k;
        // 哈希表，记录「延迟删除」的元素，key 为元素，value 为需要删除的次数
        HashMap<Integer,Integer> delayed;
        DualHeap(int k){
            this.small = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    //不可直接做相减运算，精度要求
                    return o2.compareTo(o1);
                }
            });

            this.large = new PriorityQueue<>(new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    //不可直接做相减运算，精度要求
                    return o1.compareTo(o2);
                }
            });
            this.k = k;
            this.delayed = new HashMap<>();
            this.smallSize = 0;
            this.largeSize = 0;
        }

        double getMedian(){
            return (k&1)==1?small.peek():((double)small.peek()+large.peek())/2;
        }

        void insert(int num){
            if (small.isEmpty()||num<=small.peek()){
                small.offer(num);
                smallSize++;
            }else {
                large.offer(num);
                largeSize++;
            }
            makeBalance();
        }

        // 调整 small 和 large 中的元素个数，使得二者的元素个数满足要求
        void makeBalance(){
            if (smallSize>largeSize+1){
                // small 比 large 元素多 2 个
                large.offer(small.poll());
                smallSize--;
                largeSize++;
                // small 堆顶元素被移除，需要进行 prune
                prune(small);
            }else if(smallSize<largeSize){
                small.offer(large.poll());
                smallSize++;
                largeSize--;
                // large 堆顶元素被移除，需要进行 prune
                prune(large);
            }
        }

        // 不断地弹出 heap 的堆顶元素，并且更新哈希表
        void prune(PriorityQueue<Integer> heap){
            while (!heap.isEmpty()){
                Integer num = heap.peek();
                if (delayed.containsKey(num)){
                    delayed.put(num,delayed.get(num)-1);
                    if (delayed.get(num)==0){
                        delayed.remove(num);
                    }
                    heap.poll();
                }else{
                    break;
                }
            }
        }

        void erase(int num){
            delayed.put(num,delayed.getOrDefault(num,0)+1);
            if (num<=small.peek()){
                smallSize--;
                if (num==small.peek()){
                    prune(small);
                }
            }else {
                largeSize--;
                if (num==large.peek()){
                    prune(large);
                }
            }
            makeBalance();
        }
    }
}
